package zuochengyun;

import java.util.HashSet;

import list.LinkedListCreate;
import list.ListNode;

public class DeleteRepeatNodes {

	public static void main(String[] args) {
		DeleteRepeatNodes deleteRepeatNodes = new DeleteRepeatNodes();
		
		int[] array = {1, 1, 1, 2, 3, 3, 6};
		ListNode head = LinkedListCreate.createList(array);
		LinkedListCreate.printList(deleteRepeatNodes.removeAlListNode(head));
	}
	/**
	 * 删除重复的结点 1 -- 2 -- 3 -- 3 -- 3 -- 4 >>> 1 -- 2 -- 3 --4
	 * @param head
	 */
	public void removeRepeat(ListNode head){
		if(head == null){
			return;
		}
		HashSet<Integer> set = new HashSet<>();
		ListNode pre = head;
		ListNode cur = pre.next;
		while(cur != null){
			if(set.contains(cur.val)){
				pre.next = cur.next;
			}else{
				set.add(cur.val);
				pre = cur;
			}
		}
	}
	/**
	 * 删除所有重复出现的结点 1 -- 2 -- 3 -- 3 -- 3 -- 4 >>> 1 -- 2 --4
	 */
	public ListNode removeAlListNode(ListNode head){
		if(head == null || head.next == null){
			return head;
		}
		//这道题的精髓就是创建一个新的结点，然后将头结点连入到该结点之后
		ListNode fakeHead = new ListNode(0);
		ListNode pre = fakeHead;
		ListNode cur = head;
		int val = 0;
		int i = 0;
		while(cur != null){
			val = cur.val;
			while(cur.next != null && cur.next.val == val){
				cur = cur.next;
			}
			if(pre.next == cur){
				//cur没有移动，此时就说明cur的值是独一无二的，可以将pre已知cur
				pre = cur;
			}else{
				//cur移动至重复元素的最末尾，pre.next指向该元素的下一个，既删除了所有的重复元素
				//注意这里不要移动pre
				pre.next = cur.next;
			}
			if(cur != null){
				System.out.println(i++ + " Node value " + pre.val + " " + cur.val);
			}
			cur = cur.next;
		}
		return fakeHead.next;
	}
}
